package arithmetic2;

/**
 * @author macpro
 * @date 2019-08-07
 * @function 最长公共前缀
 *
 * https://leetcode-cn.com/problems/longest-common-prefix/
 */
public class T_014_LongestCommonStr {
    public static void main(String[] args) {

        char[] temp = "a".toCharArray();
        System.out.println("a".toCharArray()[0]);
        System.out.println("a".toCharArray()[0]-97);

        System.out.println("abcd".substring(0,0));
//        System.out.println(longestCommonPrefix(new String[]{"flower","flow","flight"}));
        System.out.println(longestCommonPrefix(new String[]{"a"}));
    }

    public static String longestCommonPrefix(String[] strs) {

        //1 最长 0-n
        // 2 每个都需要遍历，每个不同就停止。 Trie 前缀树
        if (strs == null || strs.length<1)return "";
        Tire tire = new Tire();
        tire.insert(strs[0]);
        int res = strs[0].length();
        for (int i = 1; i < strs.length; i++) {
             res = tire.commonEndIndex(strs[i]);
//            System.out.println("res "+res);
        }

        return strs[0].substring(0,res);
    }



}
class Tire{
    int commonEnd ;

    TireNode root;

    Tire() {
        this.root = new TireNode();
    }

    class TireNode{
         boolean isWord;
         TireNode[] children;

        TireNode() {
            this.children = new TireNode[26];
        }
    }

    public void insert(String word){
        if (word==null || word.length()<1){
            commonEnd=0;
            return ;
        }
        TireNode temp = root;
        char[] chars = word.toCharArray();
        for (int i = 0; i < chars.length; i++) {
            int index = chars[i] - 97;
            if (temp.children[index] == null){
                temp.children[index] = new TireNode();
            }
            temp = temp.children[index];
        }
        temp.isWord = true;
        commonEnd = chars.length;
    }

    public int commonEndIndex(String prefix){
        if (prefix==null || prefix.length()<1)return 0;
        char[] chars = prefix.toCharArray();
        TireNode temp = root;

        for (int i = 0; i < chars.length; i++) {
            if (i>= commonEnd)return commonEnd;//暂停对比

            int index = chars[i] - 97;
            if ( temp.children[index] == null){
                commonEnd = i;
                return i;
            }
            temp = temp.children[index];
        }

        commonEnd = chars.length;
        return chars.length;
    }

}